//https://leetcode.cn/problems/minimum-window-substring/

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = { 0 };  //统计t中有效元素
        int hash2[128] = { 0 };  //统计滑动窗口的有效元素
        int kinds = 0;  //统计t中有效元素的种类
        int minlen = INT_MAX;
        int pos = -1;
        for (auto e : t)
        {
            if (hash1[e]++ == 0)
                kinds++;
        }

        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            //进窗口
            if (++hash2[s[right]] == hash1[s[right]]) count++;
            //判断
            while (count == kinds)
            {
                //更新结果
                if (minlen > right - left + 1)
                {
                    minlen = right - left + 1;
                    pos = left;
                }
                //出窗口
                if (hash2[s[left]]-- == hash1[s[left]]) count--;
                left++;
            }
        }
        if (pos == -1) return "";
        else return s.substr(pos, minlen);

    }
};